class Solution:
    def intervalIntersection(self, firstList: list[list[int]], secondList: list[list[int]]) -> list[list[int]]:
        res=[]
        for first in firstList:
            if len(secondList)==0:
                return res
            while len(secondList)>0:
                middle=secondList.pop(0)
                if middle[0]>first[1]:
                    secondList.insert(0,middle)
                    break
                if middle[1]<first[0]:
                    continue
                lrft=max(middle[0],first[0])
                right=min(middle[1],first[1])
                res.append([lrft,right])
                if right<middle[1]:
                    middle[0]=right+1
                    secondList.insert(0,middle)
        return res

if __name__ == '__main__':
    Solution().intervalIntersection([[0,2],[5,10],[13,23],[24,25]],
                                    [[1,5],[8,12],[15,24],[25,26]])
